package leetcode.listnode;

import leetcode.ListNode;
import leetcode.ListNodeUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Cheng Jun
 * Description: 给定一个单链表 L 的头节点 head ，单链表 L 表示为：L0 → L1 → … → Ln - 1 → Ln
 * 请将其重新排列后变为： L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 * @version 1.0
 * @date 2022/7/28 21:09
 * 字节面试题 二刷
 */
public class reorderList {

    public static void main(String[] args) {
        ListNode listNode = ListNodeUtil.getListNode(new int[]{1, 2, 3, 4});
        reorderList(listNode);
    }

    /**
     * 链表的特点就是不能快速访问节点，考虑使用 ArrayList存储
     *
     * @param head
     * @return void
     * @author Cheng Jun
     * @date 2022/7/28 21:11
     */
    static void reorderList(ListNode head) {
        List<ListNode> nodeList = new ArrayList<>();
        ListNode pointer = head;
        while (pointer != null) {
            nodeList.add(pointer);
            pointer = pointer.next;
        }
        int left = 0;
        int right = nodeList.size() - 1;
        while (left < right) {
            ListNode leftNode = nodeList.get(left);
            ListNode rightNode = nodeList.get(right);
            rightNode.next = leftNode.next;
            leftNode.next = rightNode;
            left++;
            right--;
        }
        nodeList.get((nodeList.size()) / 2).next = null;
    }

//    找到原链表的中点  将原链表的右半端反转 将原链表的两端合并。
}
